Cryptographic operations are generally implemented on elements in a finite field. Various finite fields are of interest to cryptographers for example, the multiplicative groups of prime fields F(p), the multiplicative group of finite fields of characteristic two, F(2n) and elliptic curve groups over finite fields, E(Fp) or E(F2n). The elements in a given finite field are represented in terms of a basis for the finite field. The bases are also elements of the finite field.
Certain efficiencies may be realized in cryptographic operations by choosing a particular set of bases fot that finite field. For example, in the finite field F(2n), two common choices of bases are the polynomial basis and a normal basis. A problem arises though in the choice of basis since communication between the two parties, although using the same cryptographic scheme but having different bases elements, requires the parties to perform a basis conversion operation on the field elements in order to obtain the same cryptographic result.
In general, if we let F(qn) be a finite field, where q is a prime or a prime power, the degree of the field is n and its order is qn. A basis for the finite field is a set of n elements b0, b1, . . . bn−1 εF(qn) such that every element A of the finite field can be represented uniquely as a linear combination of basis elements:
  A  =            ∑              i        =        0            n1        ⁢                  a        i            ⁢              b        i            where the ai ε F(q) are the coefficients. Arithmetic operations are then performed on this ordered set of coefficients.
It may be seen then generally that by using a different basis, a different ordered set of coefficients is used.
Various techniques have been implemented to convert between two choices of bases for a finite field. A conventional approach involves using a matrix multiplication, wherein basis conversion is performed using a change of basis matrix m, resulting in a matrix of size m2. If m is typically 160 bits, then this occupies significant storage in devices such as a smart card. General finite field techniques are described in the “Handbook of Applied Cryptography”, CRC Press, 1996 by S. A. Vanstone et al and incorporated herein by reference. Other techniques for basis conversion are described in U.S. Pat. No. 5,854,759 to Kaliski et al, also incorporated herein by reference.